#pragma once
#include <iostream>
#include <vector>
#include <cassert>

namespace xyl
{
    using std::cout;
    using std::endl;

    template <size_t N> // N这个数可以很大
    class bitset
    {
        using type = char;

    private:
        std::vector<type> _v;
        size_t _count = 0; // 记录被设置成 1 的位的个数，当被 set、reset、flip 时应该更新 count
        // N  //总共可以设置的位的个数

    public:
        bitset()
            : _v(N / sizeof(type) + 1, 0)
        {
        }

        void set(size_t pos)
        {
            assert(pos < N);
            if (!test(pos))
            {
                int i = pos / sizeof(type);
                int j = pos % sizeof(type);
                _v[i] |= (1 << j);
                ++_count;
            }
        }

        void set() // 似乎很低效......需要O(N)，暂时没想到其他方法
        {
            // for(size_t i = 0; i < N; ++i)
            //     if(!this->test(i))
            //         this->set(i);
            for (size_t i = 0; i < _v.size(); ++i)
                _v[i] |= ((1 << 8) - 1);
            _count = N;
        }

        void reset(size_t pos)
        {
            assert(pos < N);
            if (test(pos))
            {
                int i = pos / sizeof(type);
                int j = pos % sizeof(type);
                _v[i] &= ~(1 << j);
                --_count;
            }
        }

        void reset() // 似乎很低效......需要O(N)，暂时没想到其他方法
        {
            // for(size_t i = 0; i < N; ++i)
            // {
            //     if(this->test(i))
            //         this->reset(i);
            // }
            for (size_t i = 0; i < _v.size(); ++i)
                _v[i] = 0;
            _count = 0;
        }

        void flip(size_t pos)
        {
            assert(pos < N);
            int i = pos / sizeof(type);
            int j = pos % sizeof(type);
            _v[i] & (1 << j) ? --_count : ++_count;
            _v[i] ^= (1 << j);
        }

        void flip() // 似乎很低效......需要O(N)，暂时没想到其他方法
        {
            for (size_t i = 0; i < _v.size(); ++i)
                _v[i] = ~_v[i];
            _count = N - _count;
        }

        bool test(size_t pos)
        {
            assert(pos < N);
            int i = pos / sizeof(type);
            int j = pos % sizeof(type);
            return _v[i] & (1 << j);
        }

        size_t size() { return N; }
        size_t count() { return _count; }
        bool any() { return _count > 0; }
        bool none() { return _count == 0; }
        bool all() { return _count == N; }

        std::string to_string()
        {
            // 遍历 (N,0]，用 test() 判断是否被设置，然后组装字符串
            std::string s;
            s.reserve(N);
            for (size_t i = N - 1; i > 0; --i) // 注意，size_t的i为0时，再--i，会使得i又变成一个很大的正数而非-1，因此i=0时单独处理
                s.push_back(this->test(i) ? '1' : '0');
            s.push_back(this->test(0) ? '1' : '0');

            return s;
        }

        // debug
        void print()
        {
            std::cout << this->to_string() << std::endl;
        }
    };

    // /// 重载流式操作符 ,失败，暂时先不实现
    // template <size_t N>
    // std::ostream &operator<<(std::ostream &o, const bitset<N> &b)
    // {
    //     o << bitset<N>::to_string();
    //     return o;
    // }

} // namespace xyl
